#include "Expand.h"
#include <assert.h>
#include <gc/gc.h>
Multitree * expand_power(Multitree * base, Integer exponent);
/*the function is basically same as all other functions. Call it on subtrees and then do something with the current node.
It would be better probably to have it once. But how to do it?*/
Multitree * expand_tree(Multitree * tree){
	/*If current symbol is not MULTIPLY, then just recursively expand subtrees and return it.
	Otherwise do something
	We can of course use one if - is it MULTIPLY or not? But I decided to use switch again
	because i know how many childs the node has and do not need to use many ifs (for adding
	child to the end of linked list - first node must be handled differently)*/
	Multitree * to_return = NULL;
	ListOfChilds * add_to = NULL;
	ListOfChilds * pass = NULL;
	Multitree * tmp = NULL;
	Multitree * exponent = NULL;
	Multitree * base = NULL;
	double dou_power;
	int inverted;
	int int_power;
	if (tree == NULL){
		return NULL;
	}
	switch (tree->symbol.type){
		case NUMBER:
		case VARIABLE:
		case CONSTANT:
			/*No childs. Just copy it.*/
			return copy_tree(tree);
			break;
		case FUNCTION:
			/*We call expand_tree() to argument and attach it here.*/
			to_return = give_me_empty_tree();
			symbolcpy(&(to_return->symbol), &(tree->symbol));
			to_return->childs = give_me_empty_child();
			to_return->childs->next = NULL;
			to_return->childs->inverted = 0;
			to_return->childs->subtree = expand_tree(tree->childs->subtree);
			if (to_return->childs->subtree == NULL){
				return NULL;
			}
			return to_return;
			break;
		case OPERATOR:
			to_return  = give_me_empty_tree();
			symbolcpy(&(to_return->symbol), &(tree->symbol));
			/*Add there first child*/
			to_return->childs = give_me_empty_child();
			to_return->childs->inverted = tree->childs->inverted;
			to_return->childs->next = NULL;
			to_return->childs->subtree = expand_tree(tree->childs->subtree);
			if(to_return->childs->subtree == NULL){
				return NULL;
			}
			/*Add other childs*/
			add_to = to_return->childs;
			pass = tree->childs->next;
			while (pass != NULL){
				add_to->next = give_me_empty_child();
				add_to->next->inverted = pass->inverted;
				add_to->next->next = NULL;
				add_to->next->subtree = expand_tree(pass->subtree);
				if(add_to->next->subtree == NULL){
					return NULL;
				}
				add_to = add_to->next;
				pass = pass->next;
			}

			if (tree->symbol.oper == POWER){
				exponent = to_return->childs->next->subtree;
				/*if exponent is whole number*/
				if (exponent->symbol.type == NUMBER){
					if (number_is_int(exponent->symbol.number)){
						/*we know, that it is something raised to integer. If it is not 1, -1 or 0 then we should expand it
						we expand a^3 to a*a*a and then call expand_multiply to it.
						I could write one if with logical 'and', but I think this is more readable
						We can do this, since we know, that it is an integer.*/
						dou_power = numtodouble(exponent->symbol.number);
						inverted = (dou_power < 0)?1:0;
						if (inverted == 1){
							int_power = (int) (-dou_power);
						}else{
							int_power = (int) (dou_power);
						}
						if (int_power > 1){
							/*now we do something*/
							base = copy_tree(to_return->childs->subtree);
							/*we have base in base and exponent in int_power. We can delete to_return.*/
							delete_tree(to_return);
							to_return = expand_power(base, int_power);
							if(to_return == NULL){
								return NULL;
							}
							/*clean up base*/
							delete_tree(base);
							if(dou_power < 0){
								to_return = treepow(to_return, inttotree(-1));
								if(to_return == NULL){
									return NULL;
								}
							}
						} /*|exp| > 1*/
					}/*is int*/
				}/*is number*/
			}/*is power*/

			/*And now, if the symbol is multiply (either it was multiply or it is now, because of expansion of power)
			we expand it. If it is not multiply, then we just return to_return
			And we should somehow put the tree to "canonical form" before returning it.*/
			if (to_return->symbol.oper == MULTIPLY){
				tmp = to_return;
				to_return = expand_multiply(tmp);
				delete_tree(tmp);

			}
			
			tmp = canonicalize_tree(to_return);
			if(tmp == NULL){
				return NULL;
			}
			delete_tree(to_return);
			to_return = tmp;
			tmp = NULL;
			return to_return;
			break;
	}
	assert(0);
	return NULL;
}

Multitree * expand_multiply(Multitree * tree){
	/*Separate the childs.*/
	ListOfChilds * upper_plus = NULL; /*Not inverted with plus in subtree.*/
	ListOfChilds * upper_normal = NULL; /*Not inverted without plus in subtree*/
	ListOfChilds * lower_plus = NULL; /*Inverted with plus in subtree*/
	ListOfChilds * lower_normal = NULL; /*inverted without plus in subtree*/
	ListOfChilds * pass = tree->childs;
	ListOfChilds * added;
	Multitree * zero;
	ListOfChilds * first_child;
	ListOfChilds * second_child;
	Multitree * multiplied;
	ListOfChilds * pass1;
	ListOfChilds * pass2;
	ListOfChilds * newlist;
	Multitree * to_return;
	if(tree == NULL){
		return NULL;
	}
	while (pass != NULL){
		added = give_me_empty_child();
		added->subtree = copy_tree(pass->subtree);
		added->inverted = pass->inverted; /*It might not be necessary, but it makes things easier.*/
		if (pass->inverted){
			if ((pass->subtree->symbol.type == OPERATOR) && (pass->subtree->symbol.oper == PLUS)){
				added->next = lower_plus;
				lower_plus = added;
			}else{
				added->next = lower_normal;
				lower_normal = added;
			}
		}else{
			if ((pass->subtree->symbol.type == OPERATOR) && (pass->subtree->symbol.oper == PLUS)){
				added->next = upper_plus;
				upper_plus = added;
			}else{
				added->next = upper_normal;
				upper_normal = added;
			}
		}
		pass = pass->next;
	}
	/*We have them separated to boxes.
	Now what?
	We create (0+(*)) node, where * will be those that are "normal"
	means: from a*(b+c)*d we create (0+a*d)*(b+c). Then we can work with it consistently
	We put it then to upper_plus and we can forget about upper_normal.*/
	if(upper_normal != NULL){
		added = give_me_empty_child();
		added->inverted = 0; /*upper*/
		added->subtree = give_me_empty_tree(); //plus
		added->subtree->symbol.type = OPERATOR;
		added->subtree->symbol.oper = PLUS;
		added->subtree->childs = give_me_empty_child();
		/*added->subtree->childs->next is defined later*/
		
		/*first child should be 0*/
		zero = inttotree(0);
		added->subtree->childs->inverted = 0;
		added->subtree->childs->subtree = zero;
		if(upper_normal->next == NULL){
			/*Second should be either * or upper normal. Childs of * should be upper_normal*/
			added->subtree->childs->next = upper_normal;
			assert(added->subtree->childs->next->next == NULL);
		}else{
			added->subtree->childs->next = give_me_empty_child();
			added->subtree->childs->next->next = NULL;
			added->subtree->childs->next->inverted = 0;
			added->subtree->childs->next->subtree = give_me_empty_tree(); /*Multiply.*/
			added->subtree->childs->next->subtree->symbol.type = OPERATOR;
			added->subtree->childs->next->subtree->symbol.oper = MULTIPLY;
			added->subtree->childs->next->subtree->childs = upper_normal;
		}
		added->next = upper_plus;

		upper_plus = added;
	}
	upper_normal = NULL;


	/*same for lower.
	I know, that it is not very good to copy the code, but it seems as fastest way to write it.
	TODO - some code reuse*/
	if(lower_normal != NULL){

		/*first child should be 0*/
		zero = inttotree(0);
		
		added = give_me_empty_child();
		added->inverted = 1; /*lower*/
		added->subtree = give_me_empty_tree(); /*plus*/
		added->subtree->symbol.type = OPERATOR;
		added->subtree->symbol.oper = PLUS;
		added->subtree->childs = give_me_empty_child();
		/*added->subtree->childs->next is defined later*/
		added->subtree->childs->inverted = 0;
		added->subtree->childs->subtree = zero;

		if(lower_normal->next == NULL){
			/*Second should be either * or lower normal. Childs of * should be lower_normal*/
			added->subtree->childs->next = lower_normal;
			added->subtree->childs->next->inverted = 0;
			assert(added->subtree->childs->next->next == NULL);
		}else{
			added->subtree->childs->next = give_me_empty_child();
			added->subtree->childs->next->next = NULL;
			added->subtree->childs->next->inverted = 0;
			added->subtree->childs->next->subtree = give_me_empty_tree(); /*Multiply.*/
			added->subtree->childs->next->subtree->symbol.type = OPERATOR;
			added->subtree->childs->next->subtree->symbol.oper = MULTIPLY;
			added->subtree->childs->next->subtree->childs = lower_normal;
		}
		added->next = lower_plus;

		lower_plus = added;
	}




	if (upper_plus != NULL){
		/*If there is any with plus, then do something until there is only one.*/
		while (upper_plus->next != NULL){
			/*Take the first two, multiply each child with each subchild and put it back.*/
			first_child = upper_plus;
			second_child = first_child->next;
			upper_plus = second_child->next;
			/*Now we need to go through "sons"*/
					
			/*Create one simple multiply tree.*/
			multiplied = give_me_empty_tree();
			multiplied->symbol.type = OPERATOR;
			multiplied->symbol.oper = MULTIPLY;
			multiplied->childs = give_me_empty_child();
			multiplied->childs->inverted = 0;
			multiplied->childs->subtree = NULL;
			multiplied->childs->next = give_me_empty_child();
			multiplied->childs->next->inverted = 0;
			multiplied->childs->next->next = NULL;
			multiplied->childs->next->subtree = NULL;

			newlist = NULL;

			pass1 = first_child->subtree->childs;
			pass2 = NULL;
			while (pass1 != NULL){
				pass2 = second_child->subtree->childs;
				while(pass2 != NULL){
					/*We take one child from the first plus, one from the second, we combine them (using multiplied tree)
					And attach them to the newlist.*/
					added = give_me_empty_child();
					/*Set sign*/
					added->inverted = (pass1->inverted == pass2->inverted)?0:1; /*XOR*/
					/*Attach multiplication to */
					added->subtree = copy_tree(multiplied);
					added->subtree->childs->subtree = copy_tree(pass1->subtree);
					added->subtree->childs->next->subtree = copy_tree(pass2->subtree); //Tree must be copied.
					rehang_tree(added->subtree);
					added->next = newlist;
					newlist = added;
					pass2 = pass2->next;
				}
				pass1=pass1->next;
			}
			/*We have new list of childs for our first tree.
			Now we delete childs and create a new one that will be attached to the tree.*/
			delete_tree(first_child->subtree);
			delete_tree(second_child->subtree);
			GC_FREE(second_child);
			first_child->subtree = give_me_empty_tree();
			first_child->subtree->symbol.type = OPERATOR;
			first_child->subtree->symbol.oper = PLUS;
			first_child->inverted = 0; //This is, because it is UPPER!
			first_child->subtree->childs = newlist;
			//Now we can attach it back to the list.
			first_child->next = upper_plus;
			upper_plus = first_child;
		}
	}

	/*copy paste for lower_plus*/

	if (lower_plus != NULL){
		/*If there is any with plus, then do something until there is only one.*/
		while (lower_plus->next != NULL){
			/*Take the first two, multiply each child with each subchild and put it back.*/
			first_child = lower_plus;
			second_child = first_child->next;
			lower_plus = second_child->next;
			/*Now we need to go through "sons"*/
					
			/*Create one simple multiply tree.*/
			multiplied = give_me_empty_tree();
			multiplied->symbol.type = OPERATOR;
			multiplied->symbol.oper = MULTIPLY;
			multiplied->childs = give_me_empty_child();
			multiplied->childs->inverted = 0;
			multiplied->childs->subtree = NULL;
			multiplied->childs->next = give_me_empty_child();
			multiplied->childs->next->inverted = 0;
			multiplied->childs->next->next = NULL;
			multiplied->childs->next->subtree = NULL;

			ListOfChilds * newlist = NULL;

			ListOfChilds * pass1 = first_child->subtree->childs;
			ListOfChilds * pass2 = NULL;
			while (pass1 != NULL){
				pass2 = second_child->subtree->childs;
				while(pass2 != NULL){
					/*We take one child from the first plus, one from the second, we combine them (using multiplied tree)
					And attach them to the newlist.*/
					added = give_me_empty_child();
					/*Set sign*/
					added->inverted = (pass1->inverted == pass2->inverted)?0:1; /*XOR*/
					/*attach multiplication to*/ 
					added->subtree = copy_tree(multiplied);
					added->subtree->childs->subtree = copy_tree(pass1->subtree);
					added->subtree->childs->next->subtree = copy_tree(pass2->subtree);
					rehang_tree(added->subtree);
					added->next = newlist;
					newlist = added;
					pass2 = pass2->next;
				}
				pass1=pass1->next;
			}
			/*We have new list of childs for our first tree.
			Now we delete childs and create a new one that will be attached to the tree.*/
			delete_tree(first_child->subtree);
			delete_tree(second_child->subtree);
			GC_FREE(second_child);
			first_child->subtree = give_me_empty_tree();
			first_child->subtree->symbol.type = OPERATOR;
			first_child->subtree->symbol.oper = PLUS;
			first_child->inverted = 1; /*This is, because it is LOWER!*/
			first_child->subtree->childs = newlist;
			//Now we can attach it back to the list.*/
			first_child->next = lower_plus;
			lower_plus = first_child;
		}
	}

	/*Now we have upper_plus and upper_minus as we want them.*/
	if (lower_plus == NULL){
		to_return = upper_plus->subtree;
		GC_FREE(upper_plus);
		return to_return;
	}

	to_return = give_me_empty_tree();
	to_return->symbol.type = OPERATOR;
	to_return->symbol.oper = MULTIPLY;
	if (upper_plus == NULL){
		/*create 1/lower_plus*/
		to_return->childs = give_me_empty_child();
		to_return->childs->inverted = 0;
		to_return->childs->subtree = inttotree(1);
		to_return->childs->next = lower_plus;
	}else{
		to_return->childs = upper_plus;
		to_return->childs->next = lower_plus;
	}
	return to_return;
}

Multitree * expand_power(Multitree * base, Integer exponent){
	/*creates (a^n + a^(n-1)*b + ... + b^n) from (a+b)^n
	does not use binomial theorem, because it has to work also for (a+b+c+...)^n
	we make squares of the base until we are over the exponent and then we delete
	those we do not need and multiply rest.
	example: (a+b)^5
	we create (a+b)^1 = (a+b)
	(a+b)^2 = (a^2+b^2+2*a*b)
	(a+b)^4 = (a^2+b^2+2*a*b)^2 = .....
	delete (a+b) ^2
	multiply (a+b)^1 * (a+b)^4 */
	Multitree * to_return = NULL;
	int counter = 2;
	ListOfChilds * squares=NULL;
	Multitree * added = NULL;
	Multitree * tmp = NULL;
	ListOfChilds * tmpchilds = NULL;
	ListOfChilds * to_multiply = NULL;

	squares = give_me_empty_child();
	squares->next = NULL;
	squares->subtree =copy_tree(base);
	squares->inverted = 0;
	assert(exponent > 1);
	if(base == NULL){
		return NULL;
	}

	while(counter <= exponent){
		/*we take previous node, create multiply with two copies of it and expand them*/
		added = give_me_empty_tree();
		added->symbol.type = OPERATOR;
		added->symbol.oper = MULTIPLY;
		added->childs = give_me_empty_child();
		added->childs->next = give_me_empty_child();
		added->childs->next->next = NULL;
		added->childs->next->inverted = 0;
		added->childs->next->subtree = copy_tree(squares->subtree);
		added->childs->inverted = 0;
		added->childs->subtree = copy_tree(squares->subtree);
		/*added is previous * previous*/
		tmp = expand_multiply(added);
		if(tmp == NULL){
			return NULL;
		}
		delete_tree(added);
		added = canonicalize_tree(tmp);
		if(added == NULL){
			return NULL;
		}
		delete_tree(tmp);
		counter = counter * 2;
		/*now we add added to squares*/
		tmpchilds = give_me_empty_child();
		tmpchilds->inverted = 0;
		tmpchilds->subtree = added;
		tmpchilds->next = squares;
		squares = tmpchilds;
	}
	/*now we should have some powers of base in squares
	counter is now two times the biggest power of two in the list (and greater than exponent)*/
	counter = counter /2;
	/*now we go through the squares and delete those we do not need (and move those we need to another list)*/
	while (exponent !=0){
		assert(squares != NULL);
		tmpchilds = squares;
		squares = squares->next;
		if(counter > exponent){
			/*we do not need the current power*/
			delete_tree(tmpchilds->subtree);
			GC_FREE(tmpchilds);
		}else{
			/*we need that power*/
			tmpchilds->next = to_multiply;
			to_multiply = tmpchilds;
			exponent = exponent-counter;
		}
		counter = counter/2;
	}
	while(counter > 0){
		tmpchilds = squares;
		squares = squares->next;
		delete_tree(tmpchilds->subtree);
		GC_FREE(tmpchilds);
		counter = counter / 2;
	}
	/*now we should have correct powers in to_multiply list. We put it to some multiply tree and pass it to expand_multiply*/
	tmp = give_me_empty_tree();
	tmp->symbol.type = OPERATOR;
	tmp->symbol.oper = MULTIPLY;
	tmp->childs = to_multiply;
	to_return = expand_multiply(tmp);
	if(to_return == NULL){
		return NULL;
	}
	delete_tree(tmp);
	return to_return;
}

